k-meansを実装してみよう

データ分析

#機械学習

じょんすみす

2017.12.10

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

こんにちは、小澤です。

当エントリは「Machine Learning Advent Calendar 2017」の10日目のエントリです。

今回は、クラスタリング手法であるk-meansを実装してみます。

クラスタリングとは

クラスタリングは、教師なし学習の手法になります。

教師なし学習では、学習の際の指針となる正解ラベルがありません。その状態でデータの性質をみて、グループ分けするための手法となります。

クラスタリングなどの教師なし学習では、人間が与えた正解ラベルを予測できるように学習するわけではないので、必ずしも人間にとって望ましい結果になるとは限りません。

データの性質としては確かにあっているけどその基準で分けて欲しいわけじゃなかった、という結果になったり、そもそも何を基準にデータを分けたのかが人間には理解できないこともあります。

そのような、うまく制御できない手法がいったいどこで使えるというのでしょうか？

これはまず、データやそれが生成されたドメインに関する知識が乏しい状態で分析を始める必要がある場合に、大まかな傾向を掴みたいといった場面が考えられます。おおよそデータがどういった分布になるだろうとか、どの特徴が精度の向上に効きそうかといった、要素が何もわかっていない状況で最初にデータの性質を知るために利用できるでしょう。

次に、「人間は気がつかなかった発見」というものを見つける可能性がある点が挙げられます。これは、先ほどの「何を基準にデータを分けたのかが人間には理解できない」の裏返しではありますが、それが役に立つ場面もあります。例えば、非常に有名な例として以下のようなものが挙げられます。

"アメリカのスーパーマーケットでデータ分析をしたところ、休日前の夕方にビールと紙おむつを一緒に買う人が非常に多くいた"

これ自体は、ある種の都市伝説のように語られており、それがわかってどのような施策を行ったかについても様々な説があります。しかし、データ分析によって意外なことがわかった例として非常に有名なものになります。

このように意外な発見というものが見つかるもしれません。ただし、こちらに関しては過度に期待するべきものではりません。あくまでもデータから抽出した傾向を出すものなので、多くの場合で「夏にはサンダル、冬にはブーツがよく売れることがわかった」など、当然のことが発見されることになります(あたりまえのことなので、当然データにもその傾向が含まれます)。

なお、この一緒に買われる商品を分析した手法は今回紹介するk-meansではなく、aprioriというものになります。

k-meansとは

k-meansはクラスタリングの中でも比較的わかりやすい手法です。

やることとして、以下のような操作になります。

分割対象となるクラスタ数kを決める
データが含まれる空間にランダムにk個の点(セントロイド)を置くき、それぞれのクラスタの中心とする
各データがセントロイドのうちどれに最も近いかを計算して、そのデータが所属するクラスタとする
セントロイドの位置をそのクラスタに含まれるデータの重心になるように移動する
各セントロイドの重心が変わらなくなるまで3, 4を繰り返す

k-meansを扱う上で、１つ注意点があります。それは、初期値をランダムに決めているのでその値によって結果が変わってしまう可能性があるということです。そのため、何回か実行してみてその結果の多数決で所属クラスタを決めるなどの工夫が必要になる場合があります。

実装してみる

さて、実装してみましょう。

利用するデータ

今回は実行的に生成した、以下のデータを使ってみます。ええ、どういう結果になりそうかわかりやすそうですね。

中身は単純で3つの異なる分布から乱数で生成されたデータになります

def create_data(size, x_mean, x_stddiv, y_mean, y_stddiv):
    data = random.randn(size, 2)
    for i in data:
        i[0] = i[0] * x_stddiv + x_mean
        i[1] = i[1]  * y_stddiv + y_mean
    return data
    
cluster1 = create_data(100, 2, 0.5, 2, 1)
cluster2 = create_data(100, -2, 0.5, 0, 0.5)
cluster3 = create_data(100, 2, 1, -2, 0.5)

実装

さて、比較的簡単な手法なので実装の方も一気に見てみましょう。今回は２次元固定で扱っています。

def k_means(n_cluster, data, iteration=100):
    # 初期値
    centroid = np.zeros([3, 2])
    clusters = random.randint(3, size=data.shape[0])
    
    # イテレーション
    for _ in range(iteration):
        # 重心を設定
        for c in range(n_cluster):
            new_c = np.array([j for i, j in zip(clusters, data) if i == c]).mean(axis=0)
            centroid[0] = new_c[0]
            centroid[1] = new_c[1]
            
        # 重心に基づいてクラスタを変更
        clusters = np.array([min([(index, (i[0] - j[0])**2 + (i[1] - j[1])**2) for index, j in enumerate(centroid)], key=lambda d : d[1]) for i in data])[:, 0]
        
    return clusters
    
df['cluster'] = k_means(3, df.as_matrix(), 100)
df['cluster_name'] = df.cluster.map(lambda x: 'cluster_{}'.format(int(x)))

重心の計算は、各軸ごとの平均値を求めることで出しています。

[latex] \mu_x = \frac{1}{n}\sum_{i=0}^N x_i \\ \mu_y = \frac{1}{n}\sum_{i=0}^N y_i [/latex]

データと各セントロイドとの距離は

[latex] \sqrt{(x_i - x_{centroid})^2 + (y_i - y_{centroid})^2} [/latex]

でも求められるので、その値が一番小さいセントロイドを取り出します。なお、距離そのものを知りたいわけではなく大小関係を比較するため、平方根をとっても取らなくても結果は変わらないので取ってません。

k-meansはこの辺、簡単な数式しか出てこないので落ち着きますね。